package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/8.<br><br>
 *
 * 两数之和 IV - 输入 BST
 */
public class Topic653 {
    public static void main(String[] args) {
        Topic653 instance = new Topic653();

        List<Integer> list = Arrays.asList(5,3,6,2,4,null,7);
        TreeNode root = Util.createTree(list);
        System.out.println(instance.findTarget(root, 9));

        list = Arrays.asList(5,3,6,2,4,null,7);
        root = Util.createTree(list);
        System.out.println(instance.findTarget(root, 28));

        list = Arrays.asList(2,1,3);
        root = Util.createTree(list);
        System.out.println(instance.findTarget(root, 4));

        root = Util.createTree(list);
        System.out.println(instance.findTarget(root, 1));

        root = Util.createTree(list);
        System.out.println(instance.findTarget(root, 3));
    }

    public boolean findTarget(TreeNode root, int k) {
        return travel(root, root, k);
    }

    private boolean travel(TreeNode root, TreeNode cur, int k) {
        if(cur == null) {
            return false;
        }

        return find(root, cur.val, k - cur.val) || travel(root, cur.left, k) || travel(root, cur.right, k);
    }

    private boolean find(TreeNode root, int value, int k) {
        if(root == null || value == k) {
            return false;
        }

        if(k < root.val) {
            return find(root.left, value, k);
        }
        else if(k > root.val) {
            return find(root.right, value, k);
        }
        else {
            return true;
        }
    }

    public boolean findTarget2(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return findTarget(root, k, set);
    }

    private boolean findTarget(TreeNode root, int k, Set<Integer> set) {
        if(root == null) {
            return false;
        }

        if(set.contains(k - root.val)) {
            return true;
        }

        set.add(root.val);
        return findTarget(root.left, k, set) || findTarget(root.right, k, set);
    }
}
